:) kompletny kretyn: Jak to COŚ rozwiązać? 13 x ≡ 1 mod 23 Tzn. Jak z tego czegoś x wyznaczyć.

Jack: 13x ≡ 1 (mod 23) Chcemy przemnożyć obie strony przez taką liczbę a, że a *13≡ 1 (mod 23), czyli przez liczbę odwrotną do 13 mod 23. Skorzystamy z algorytmu Euklidesa, aby ją znaleźć (a istnieje, ponieważ NWD(13,23)=1). Po kilku przekształceniach otrzymujemy: 1=17*23−30*13 1≡−30*13 (mod 23) stąd szukane a=−30≡16 (mod 23) (sprawdzamy, że 13*16=208≡1 (mod 23) ) Zatem x≡ 16 (mod 23) ⇔ (z def. kongruencji ) x= 23k +16 , gdzie k∊Z.

kompletny kretyn: Dzięki Dobry jesteś z tej matmy